package com.atguigu.chapter14


/**
 *
 * @description: xxx
 * @time: 2020-05-29 14:59
 * @author: baojinlong 
 **/
object RecursiveDemo03 {
  def main(args: Array[String]): Unit = {
    println(myMax(List(1, 2, 3, -1, 9, 112)))
    println(myReverse("abcdefgh"))
    println(factorial(5))
    println(myFbn(3))
  }

  /**
   * 使用递归求List中最大元素
   *
   * @param xs 输入的集合
   * @return
   */
  def myMax(xs: List[Int]): Int = {
    if (xs.isEmpty) {
      throw new java.util.NoSuchElementException
    }
    if (xs.size == 1) {
      xs.head
    } else if (xs.head > myMax(xs.tail)) {
      xs.head
      // 递归是告诉计算机做什么,而不是告诉计算机怎么做
    } else {
      myMax(xs.tail)
    }
  }

  /**
   * 使用递归的方式实现字符串翻转
   *
   * @param xs
   * @return
   */
  def myReverse(xs: String): String = {
    if (xs.length == 1) {
      xs
    } else {
      myReverse(xs.tail) + xs.head
    }
  }

  /**
   * 通过递归方式求阶乘
   *
   * @param n
   * @return
   */
  def factorial(n: Int): Int = {
    if (n == 0) {
      1
    } else {
      n * factorial(n - 1)
    }
  }

  /**
   * 递归的调用次数是指数增长的.
   *
   * @param n
   * @return
   */
  def myFbn(n: BigInt): BigInt = {
    if (n == 1 || n == 2) {
      1
    } else {
      myFbn(n - 1) + myFbn(n - 2)
    }
  }

}
